/*
12. 判断子序列
2022-11-2
link:https://leetcode.cn/problems/is-subsequence/
question:
	给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
	字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
	（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
answer:
	这道题目算是“编辑距离”的入门题目（毕竟这里只是涉及到减法），也是动态规划解决的经典题型。
	双指针可以解决，时间复杂度O(n).
	动态规划五步曲：
	1、dp数组和下标含义：
		dp[i][j] 表示以下标i-1为结尾的字符串s，
		和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
	2、递推公式
		if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;
		因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1
		（如果不理解，在回看一下dp[i][j]的定义）
		if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，
		那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了。
		即：dp[i][j] = dp[i][j - 1];
	3、初始化
		dp[i][0] 表示以下标i-1为结尾的字符串，与空字符串的相同子序列长度，所以为0.
		dp[0][j]同理。
	4、遍历顺序
		遍历顺序是从上到下，从左到右
	5、举例推导
*/
func isSubsequence(s string, t string) bool {
	// dp数组和初始化
	dp := make([][]int, len(s)+1)
	for i := 0; i <= len(s); i++ {
		dp[i] = make([]int, len(t)+1)
	}
	// 遍历顺序
	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(t); j++ {
			if s[i-1] == t[j-1] { // 注意这里不同字符串，索引不一样！
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = dp[i][j-1]
			}
		}
	}
	return dp[len(s)][len(t)] == len(s) // go不支持负数索引
}